A. Technical Field
The present invention relates generally to multiple match circuits, and more particularly, to multiple match circuits in content addressable memory devices.
B. Background of the Invention
Current trends in memory devices are resulting in larger, faster, and better performing memory products. Certain special purpose memory devices, such as content addressable memory (“CAM”) devices have been and are being developed to address these memory requirements.
A CAM device may operate as a cache memory and retrieve stored data by comparing an input word to pre-stored word entries so that one or more “matches” may be identified within the memory device. Based on the result of this comparison, an output on the CAM device provides an address(es) or memory location(s) associated with the matching word entry or entries. Various CAM devices provide an output on which a match signal is generated, which indicates that at least one word entry in the CAM matched the input word.
In some applications, the address of the pre-stored word entry having the highest priority is required. For example, in a CAM with 256-entries, address 0 through address 255, the address 0 may be assigned the highest priority. During a compare operation, if both addresses 144 and 11 match the word entry, the higher priority address or “priority-encoded address” would be the location with the higher priority.
In certain other applications, the priority-encoded address may not be required. As a result, a word entry may have multiple matches which may generate different outputs depending on the particular implementation of the CAM device. In one example, a “don't care” bit is generated that represents the priority-encoded address output. During such an occurrence, a signal emphasizing the fact that two or more matching data entries in the memory need to be asserted. This signal is known within the art as a “multiple match” signal.
An exemplary CAM block diagram is shown in FIG. 1 which illustrates an n-entry CAM array 102 that stores word entries. An input word 112, which needs to be compared with the pre-stored word entries, is provided to the n-entry CAM array 102. A plurality of hitlines 103 are provided, each corresponding to a word entry within the CAM array 102, which may be asserted if the input word 112 matches a particular stored word entry. The hitlines 103 interface with a match circuit 104, which provides information on matching of any pre-stored word entry. Typically, no information regarding the matching of 2 or more entries is obtained from the output match 114 signal of the match circuit 104.
The hitlines 105 may further be connected to a multiple match circuit 106. If two or more of the word entries in the CAM are found to match the input word 112, a multiple match 116 signal is asserted by the multiple match circuit 106. Hitlines 107 may further connect to an n-entry address encoder 108. A priority-encoded address may be calculated and output through the encoded address 118 signal. One skilled in the art will recognize that an analysis of the match signal 114, the multiple match signal 116 and the encoded address signal 118 is required to obtain a complete understanding of the total number of matches and a corresponding address(es) of the match.
A multiple match signal indicating the presence of two or more matches may be generated by using an analog comparator in a multiple-match detect circuit as shown in FIG. 2. A CAM memory having “n” number of pre-stored word entries may provide inputs to the multiple-match detect circuit in form of hit-lines 206. Two dedicated separate bitlines X1 202 and X1N 204 may be used for comparison in a comparator circuit 218. In particular, the bitline X1 202 may connect to n pull-up transistors and the bitline X2 204 may connect to n pull-down transistors.
Upon the occurrence of a single match, one of the pull down and one of the pull-up transistor are activated. The comparator circuit 218 compares the pull-up and the pull-down strength as per the current in the bitlines X1 202 and X1N 204. If there are two or more hits in the CAM memory, then two of the pull-up transistors and corresponding two pull-down transistors are turned on. The comparator may thus compare the pull-up strength and the pull-down strength in case of a single hit and multiple hit to distinguish between the two occurrences.
The use of an analog multiple match circuit may not yield accurate result when used with shrinking semiconductor technology applications, such as those applications using 90-nanometer and beyond manufacturing technologies. Device mismatch and leakage current increase as the fabrication constraints become increasingly more stringent. These mismatches and leakage currents make the comparison using the pull-down strength and the pull-up strength more error prone, which results in more inaccuracy in the multiple-match signal.
A digital circuit, comprising static AND/OR logic gates, may be used to implement a multiple match device. Generally, such a circuit may be implemented as an n-bit wide hierarchical AND/OR logic tree. A “Hit” and a “Multiple Hit” signal may be generated for every pair of words. A “Hit” means there is at least one match among the two words, and a signal on a corresponding hitline may be asserted. If multiple words in the CAM are found matching, then a Multiple Hit signal is asserted.
In one example, hitlines HL0 and HL1 are provided and correspond to signals from word 0 and word 1. A single hitline “H2” and multiple hit line “M2” are defined as follows:                H2=HL0 OR HL1        M2=HL0 AND HL1        
The “hitline” signal H2 and the “multiple-hit” signal M2 may be used to generate a hit signal “H4” and a multiple hit signal M4 corresponding to a second level in a signaling hierarchy. This may be implemented using the hit and multiple hit signals H2T/M2T corresponding to the top pair of words and H2B/M2B corresponding to the bottom pair of words. As a result, H4 and M4 may be defined as:                H4=H2T OR H2B        M4=(H2T AND H2B) OR (M2T OR M2B)        
These defined signals may be used in a hierarchical nature to produce a multiple match signal corresponding to numerous stored CAM word entries. Although the static gate implementation provides a robust method for implementing the multiple match function, the implementation may not be effectively used in high-speed applications above 800 MHz because of the number and speed of digital operations required in the identification of multiple matching instances.